#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

/* O(n^3) */
int algo1(int *a, int n)
{
    int i, j ,k, sum, max;

    max = 0;
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            sum = 0;
            for (k = i; k <= j; k++) {
                sum += a[k];
            }

            if (sum > max)
                max = sum;
        }
    }

    return max;
}

/* O(n^2) */
int algo2(int *a, int n)
{
    int i, j, sum, max;

    max = 0;
    for (i = 0; i < n; i++) {
        sum = 0;
        for (j = i; j < n; j++) {
            sum += a[j];
            if (sum > max)
                max = sum;
        }
    }

    return max;
}

int algo_child(int *a, int l, int r)
{
    int i, m, max, rsum, lsum, rmax, lmax;

    if (l > r)
        return 0;

    if (l == r)
        return (a[l] > 0)?a[l]:0;

    m = (l+r)/2;
    for (i = m, lsum = lmax = 0; i >= l; i--) {
        lsum += a[i];
        if (lsum > lmax)
            lmax = lsum;
    }

    for (i = m+1, rsum = rmax = 0; i <= r; i++) {
        rsum += a[i];
        if (rsum > rmax)
            rmax = rsum;
    }

    max = lmax + rmax;
    if ((lmax = algo_child(a, l, m)) > max)
        max = lmax;
    if ((rmax = algo_child(a, m+1, r)) > max)
        max = rmax;

    return max;
}

/* O(n * log n) */
int algo3(int *a, int n)
{
    return algo_child(a, 0, n-1);
}

/* O(n) */
int algo4(int *a, int n)
{
    int i, max, maxendinghere;

    max = maxendinghere = 0;
    for (i = 0; i < n; i++) {
        if (maxendinghere+a[i] > 0)
            maxendinghere += a[i];
        else
            maxendinghere = 0;

        if (maxendinghere > max)
            max = maxendinghere;
    }
    
    return max;
}

int main(int argc, char *argv[])
{
    int *a, max, i, n;
    struct timeval tv1, tv2;
    
    puts("Input n:");
    while (scanf("%d", &n)) {
        a = malloc(sizeof(int) * n);
        srand(time(NULL));
        for (i = 0; i < n; i++) {
            a[i] = rand()/100 - 50;    
        }

    gettimeofday(&tv1, NULL);
    max = algo4(a, n);
    gettimeofday(&tv2, NULL);
    printf("%d, algo4 used %ld nsec\n", max, 
        (tv2.tv_sec - tv1.tv_sec)*1000000+(tv2.tv_usec - tv1.tv_usec));

    gettimeofday(&tv1, NULL);
    max = algo3(a, n);
    gettimeofday(&tv2, NULL);
    printf("%d, algo3 used %ld nsec\n", max, 
        (tv2.tv_sec - tv1.tv_sec)*1000000+(tv2.tv_usec - tv1.tv_usec));


    gettimeofday(&tv1, NULL);
    max = algo2(a, n);
    gettimeofday(&tv2, NULL);
    printf("%d, algo2 used %ld nsec\n", max, 
        (tv2.tv_sec - tv1.tv_sec)*1000000+(tv2.tv_usec - tv1.tv_usec));
     

    gettimeofday(&tv1, NULL);
    max = algo1(a, n);
    gettimeofday(&tv2, NULL);
    printf("%d, algo1 used %ld nsec\n", max, 
        (tv2.tv_sec - tv1.tv_sec)*1000000+(tv2.tv_usec - tv1.tv_usec));

        free(a);
        puts("Input n:");
    }
    return 0;
}
